As far from land as possible

Time: O(MxN); Space: O(MxN); medium

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: grid =

[
    [1, 0, 1],
    [0, 0, 0],
    [1, 0, 1]
]

Output: 2

Explanation:

  • The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: grid =

[
    [1, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]

Output: 4

Explanation:

  • The cell (2, 2) is as far as possible from all the land with distance 4.

Notes:

  • 1 <= len(grid) = len(grid[0]) <= 100

  • grid[i][j] is 0 or 1

[1]:

import collections

class Solution1(object):
    """
    Time:  O(m * n)
    Space: O(m * n)
    """
    def maxDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        q = collections.deque([(i, j) for i in range(len(grid))
                                      for j in range(len(grid[0])) if grid[i][j] == 1])
        if len(q) == len(grid) * len(grid[0]):
            return -1
        level = -1
        while q:
            next_q = collections.deque()
            while q:
                x, y = q.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if not (0 <= nx < len(grid) and
                            0 <= ny < len(grid[0]) and
                            grid[nx][ny] == 0):
                        continue
                    next_q.append((nx, ny))
                    grid[nx][ny] = 1
            q = next_q
            level += 1
        return level

[2]:

s = Solution1()
grid = [
    [1, 0, 1],
    [0, 0, 0],
    [1, 0, 1]
]
assert s.maxDistance(grid) == 2
grid = [
    [1, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
assert s.maxDistance(grid) == 4

[3]:

import collections

class Solution2(object):
    def maxDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        queue = collections.deque([])
        rows = len(grid)
        cols = len(grid[0])
        for i in range(rows):
            for j in range(cols):
                if grid[i][j]:
                    queue.append((i, j))

        if len(queue) == rows * cols or len(queue) == 0:
            return -1

        while queue:
            x, y = queue.popleft()
            for i, j in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if (0 <= i < rows) and (0 <= j < cols):
                    if grid[i][j] == 0:
                        grid[i][j] = grid[x][y] + 1
                        queue.append((i, j))
        return max([max(row) for row in grid]) - 1

[4]:

s = Solution2()
grid = [
    [1, 0, 1],
    [0, 0, 0],
    [1, 0, 1]
]
assert s.maxDistance(grid) == 2
grid = [
    [1, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
assert s.maxDistance(grid) == 4